<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>归并排序</title>
</head>
<body>
<h3>归并排序</h3>
<script>
	function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}
	console.log( mergeSort([1,3,2,3,5,10,15,8,7,6,22]) )
</script>
</body>
</html>
